1. Field of the Invention
The present invention relates to counters and to pseudorandom sequence generators. In particular, the present invention relates to linear feedback shift registers used to generate pseudorandom sequences and to ancillary logic and/or operations used to detect errors that may occur in the generated sequences.
2. Discussion of the Related Art
A variety of counters and linear feedback shift registers (“LFSR”) used to generate pseudorandom sequences are known. In general, a shift register with a special feedback circuit is used to generate an output sequence. Feedback circuits typically perform XOR operations on specific bits. The LFSR can circulate through (2n−1) states for an n-bit register.
An n-bit LFSR is an n-bit shift register with feedback to its input. The feedback may be formed by XORing the outputs of selected stages of the shift register, referred to as ‘taps,’ and then inputting this to the least significant bit (stage 0). Each stage has a common clock. The ‘linear’ part of the term “LFSR” derives from the fact that XOR and XNOR are linear functions.
An exemplary prior art LFSR 100A is shown in FIG. 1A. As seen, there are five stages marked 0, 1, 2, 3, 4. Arranged in sequence, each stage has an input D and an output Q. Interior stages (1, 2, 3) are connected, output Q to input D. In the output stage 4, the output Q is connected both to the OUTPUT and to an XOR gate input. A second XOR gate input is the output of stage 1. The input to the input stage (stage 0, least significant bit) is feedback from the XOR gate output.
The registers of the LFSR are frequently one bit memory devices. Shown here are D flip-flop registers. The D flip-flop tracks the input, making transitions which match those of the input D. The D stands for “data”; this flip-flop stores the value that is on the data line. As seen, the result may be clocked. FIG. 1B shows a state and output table 100B for the machine of FIG. 1A.